package com.yvon.service.demo.algorithm.offer;

/**
 * 丑数
 * 我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
 */
public class P49 {
    /**
     * <img src="https://img-blog.csdnimg.cn/20190531085609710.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTAxOTE1,size_16,color_FFFFFF,t_70"/>
     */
    class Solution {
        public int nthUglyNumber(int n) {
            int[] dp = new int[n];
            dp[0] = 1;
            int p2 = 0;
            int p3 = 0;
            int p5 = 0;
            for (int i = 1; i < n; i++) {
                int next2 = dp[p2] * 2;
                int next3 = dp[p3] * 3;
                int next5 = dp[p5] * 5;
                dp[i] = Math.min(next2, Math.min(next3, next5));
                if (dp[i] == next2) {
                    ++p2;
                }
                if (dp[i] == next3) {
                    ++p3;
                }
                if (dp[i] == next5) {
                    ++p5;
                }

            }
            return dp[n - 1];
        }


    }

}
